|
|
CS 116 Tutorial 5 (Solutions): Accumulative Recursion and Generative Recursion
Reminders:
- Assignment 05 is due on Wed, Feb 26th at 10am
-
Write an accumulatively recursive function record_digit(n)
that returns a list of integers of length 10, with each index from 0 to 9
represents a corresponding digit's total appearances in the integer
n.You cannot use L.count().
For example,
record_digit(19990514)=>[1,2,0,0,1,1,0,0,0,3]
Solution:
import check
def record_digit_acc(s,i,acc):
'''
returns a list of natural numbers indicating the appreances of each digit in s,
by going through every index i of s and mutating a 10-element list acc.
Effects: acc is mutated.
record_digit_acc: Str Nat (listof Nat) -> (listof Nat)
Requires:
* i == 0
* len(acc) == 10
* acc.count(0)==10
'''
if i == len(s):
return acc
else:
acc[int(s[i])]+=1
return record_digit_acc(s,i+1,acc)
def record_digit(n):
'''
returns a list of natural numbers indicating the appreances of each digit in
n.
record_digit: Nat -> (listof Nat)
Examples:
record_digit(0) => [1,0,0,0,0,0,0,0,0,0]
record_digit(1234567890) => [1,1,1,1,1,1,1,1,1,1]
'''
acc = [0]*10
return record_digit_acc(str(n),0,acc)
# Tests
check.expect("record_digit1",record_digit(0),[1,0,0,0,0,0,0,0,0,0])
check.expect("record_digit2",record_digit(1234567890),[1,1,1,1,1,1,1,1,1,1])
check.expect("record_digit3",record_digit(19990514),[1,2,0,0,1,1,0,0,0,3])
check.expect("record_digit4",record_digit(333),[0,0,0,3,0,0,0,0,0,0])
Write an accumulatively recursive function count_max that consumes a nonempty list
of numbers alon and returns the number of times the largest number in alon
appears.
For example,
count_max([1, 3, 5, 4, 2, 3, 3, 3, 5]) => 2
since the largest element of the list, 5 appears twice. Your function should pass
through the list only once.
import check
def count_max_acc(lst, max_so_far, occurrences):
''' count_max_acc(lst, max_so_far, occurrences) returns occurences + the number
of times max_so_far appears in lst if max_so_far >= maximum value in lst;
or returns the number of time the maximum values in lst occurs if
max_so_far < maximum value in lst.
count_max_acc: (listof Int) Int Nat -> Nat '''
if lst == []:
return occurrences
elif lst[0] > max_so_far:
return count_max_acc(lst[1:], lst[0], 1)
elif lst[0] == max_so_far:
return count_max_acc(lst[1:], max_so_far, (occurrences+1))
else:
return count_max_acc(lst[1:], max_so_far, occurrences)
def count_max(alon):
''' count_max(alon) returns the number of occurrences of
the largest number in alon.
count_max: (listof Int) -> Nat
requires: alon is non empty
Examples:
count_max([-4]) => 1
count-max([1, 3, 5, 4, 2, 3, 3, 3, 5]) => 2 '''
return count_max_acc(alon[1:], alon[0], 1)
# Tests for count_max
check.expect("Q2T1", count_max([-4]), 1)
check.expect("Q2T2", count_max([4, 4, -1]), 2)
check.expect("Q2T3", count_max([-7, -8, 12]), 1)
check.expect("Q2T4", count_max([1, 3, 5, 4, 2, 3, 3, 3, 5]), 2)
Write a function smaller consumes a non-empty string called s containing
only numeric characters by repeatedly removing the larger of the first and last characters in s .
if the first and the last number are the same, remove the last one.
For example, starting from "5284, compare "5" and "4", and recurse on
"284", which will compare "2" and "4", and recurse on "28".
Comparing "2" and "8", leads to recursing on "2", which is the answer
(since it is a string of length 1).
Note: min is not allowed to use in this question.
For example:
smaller("4325") => "2"
smaller("1") => "1"
smaller("2325") => "2"
Solution:
import check
def smaller(s):
''' smaller(s) returns the single digit obtained by repeatedly removing the
larger of the first or last digits in the list, or the last one if
they are the same.
smaller: Str -> Str
requires: len(s) > 0
s contains only digits
Examples:
smaller("1") => "1"
smaller("5284") => "2" '''
if len(s) == 1:
return s
else:
first = int(s[0])
last = int(s[-1])
if first <= last:
return smaller(s[:-1])
else:
return smaller(s[1:])
# Tests
check.expect("T1", smaller("1"), "1")
check.expect("T2", smaller("5284"), "2")
check.expect("T3", smaller("123456"), "1")
check.expect("T4", smaller("99999"), "9")
check.expect("T5", smaller("12121"), "1")
check.expect("T6", smaller("9321123"), "1")
-
Given a list L of positive integers, what is the skip-value of the list?
- If
L is empty,the skip value is 0.
- If
L is not empty:
- Add one to the current skip value
- Move ahead in the list by
n (where n is the first element in the list) and repeat the process
Write a function skip_value to calculate the skip value of the list L.
For example:
skip_value([]) => 0
skip_value([1,1,1]) => 3
skip_value([2,100,1]) => 2
Solution:
import check
def skip_value(L):
''' skip_value(L) returns the skip value of a list of positive integers L.
skip_value: (listof Nat) -> Nat
requires: elements in L are positive integers
Examples:
skip_value([]) => 0
skip_value([1,1,1]) => 3 '''
if L == []:
return 0
else:
next_step = L[0]
if next_step > len(L):
return 1
else:
return 1+skip_value(L[next_step:])
# Tests
check.expect("Skip-T1", skip_value([]), 0)
check.expect("Skip-T2", skip_value([1,1,1]), 3)
check.expect("Skip-T3", skip_value([2,100,1]), 2)
-
Develop an accumulatively recursive function list_to_num that consumes a nonempty list,
digits, of integers between 0 and 9, and returns the number corresponding to digits.
For example,
list_to_num([9, 0, 8]) => 908
list_to_num([8, 6]) => 86.
list_to_num([0, 6, 0]) => 60.
Solution:
import check
def list_to_num_acc(dig, num_so_far):
''' list_to_num_acc(dig, num_so_far) adds the digits in dig
to the end of num_so_far, eventually returns natural number,
which is the newest num_so_far
list_to_num_acc: (listof Nat) Nat -> Nat
'''
if dig == []:
return num_so_far
else:
num_so_far = (10 * num_so_far) + dig[0]
return list_to_num_acc(dig[1:], num_so_far)
def list_to_num(digits):
''' list_to_num(digits) builds a number from its list of digits
list_to_num: (listof Nat) -> Nat
requires: digits is nonempty
number in digits is between 0 to 9
Examples:
list_to_num([9, 0, 8]) => 908
list_to_num([8, 6]) => 86 '''
return list_to_num_acc(digits, 0)
# Tests
check.expect("Q1T1", list_to_num ([9, 0, 8]), 908)
check.expect("Q1T2", list_to_num([0]), 0)
check.expect("Q1T3", list_to_num([8, 6]), 86)
|